package com.leo.datastruct.tree;

/**
        带路径压缩的并查集
 * @author xuexiaolei
 * @version 2017年12月13日
 */
public class UnionFindSet {
    /**
     * 维护指向父节点的指针
     */
    private int[] mParents;
    private int mCount;

    /**
     * 初始化数组，默认每个节点都是区域头节点，即指针指向自己
     * @param capacity
     */
    public UnionFindSet(int capacity){
        mCount = capacity;
        mParents = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            mParents[i] = i;
        }
    }

    /**
     * 查找P节点的区域头结点
     * @param p
     * @return
     */
    public int find(int p){
        if (p<0 || p>=mCount){
            throw new RuntimeException("越界喽");
        }
        while (p != mParents[p])
        {
            // 将p节点的父节点设置为它的爷爷节点
            mParents[p] = mParents[mParents[p]];
            p = mParents[p];
        }
        return p;
    }

    public boolean isConnect(int a, int b){
        return find(a)==find(b);
    }

    /**
     * 联合，将a,b节点的区域头结点联合即可
     * @param a
     * @param b
     */
    public void union(int a, int b){
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot == bRoot){
            return;
        }
        mParents[bRoot] = aRoot;
    }
}
